This application is being filed with a microfiche appendix of computer program listings consisting of one (1) fiche having 42 frames.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates to halftoning by error diffusion, enhanced so as to reduce the presence of structural artifacts in the halftoned output while avoiding an artificial increase in halftoning image noise. Specifically, error diffusion according to the invention divides the input gray level intensity range into different segments for purposes of both thresholding and error diffusion. Different error diffusion threshold masks are applied for each respective segment, and different error diffusion weights are applied for each respective segment, with a decision being made as to whether or not to apply a different threshold mask being based on the local image gradient of the image.
Error diffusion halftoning, as generally described in the seminal works by Floyd, Steinberg and Stucki, has become one of the most popular techniques for producing halftoned image output based on a continuous tone image input. Particularly in connection with computerized images, where each input pixel is represented by multi-level data such as an 8-bit gray scale or 24-bit color value, error diffusion halftoning has been found to yield pleasing results in images printed with binary or limited level output printers such as color ink jet printers and the like. Error diffusion tends to enhance edge sharpness and further tends to preserve fine image detail while yielding an overall pleasing image.
Generally speaking, error diffusion proceeds in accordance with the following steps. First, a pixel in the continuous tone image is compared against a threshold (or ranges of thresholds for an output device with several levels) so as to determine what output value should be printed by the image output device. For example, in the case of a binary printer (meaning a printer that outputs at each pixel either a dot or an absence of a dot), the threshold may be xc2xd of the intensity range, with a pixel being printed if the continuous tone value exceeds xc2xd and with no pixel being printed if the continuous tone value does not exceed xc2xd. Then, the error between the continuous tone input and the actual output value is calculated. This error is diffused to adjacent pixels using predetermined weighting coefficients, so that predesignated proportions of the error are added to the original image value of adjacent pixels. Processing then proceeds with another pixel in a predetermined scan direction. When it comes time to threshold one of the adjacent pixels so as to determine whether or not to print a dot, the determination is based on the original value plus any accumulated errors.
Because of the exceedingly good image output obtained from error diffusion halftoning, a tremendous amount of effort has been expended on variations of the basic Floyd Stucki Steinberg technique so as to yield images of improved quality. Thus, various researchers have proposed changes to thresholding, changes to error diffusion coefficients, and changes in scan patterns, so as to improve error diffusion output.
Despite the amount of research aimed at error diffusion, there are several lingering problems. One of these problems concerns the formation of artifacts in the halftoned output. These artifacts form when error diffusion leads to repetitive output. Repetitive output can cause worm-like structural artifacts to appear in the halftoned output, particularly in areas of highlights such as extremely light or dark areas of an image. FIG. 1, for example, is the output 10 from conventional error diffusion halftoning, for each of 24 gray patches representing the first 24 out of 256 continuous tone gray levels. As seen in FIG. 1 at extremely light gray level highlights, repetitive output has caused worm-like artifacts such as those at 11 and 12.
Repetitive output can also cause regular patterns such as a checkerboard pattern to appear in the output. For example, FIG. 2 is the output of conventional error diffusion halftoning for a continuous tone gray wedge that varies from full dark gray (or black) to full light gray (or white). As seen at 50% gray, the halftoned output 16 has a regularized checkerboard artifact caused by repetitive output. The same artifact can be seen to a lesser degree at 25% gray and 75% gray.
Both kinds of structural artifacts are visually distracting and detract from the overall quality of the image. Moreover, in connection with color printing, the existence of regular patterns such as a checkerboard pattern can, when color components are overlaid, result in severe color shifts which manifest themselves as discolored halos of color around solid or gradually varying color regions. These structural artifacts manifest themselves in particularly displeasing ways at intensity values corresponding to integral fractions of the intensity range. Thus, a severe structural artifact is created at a intensity value of xc2xd (i.e., 50% gray), with structural artifacts of lesser visibility being observed at ⅓, ⅔, xc2xc, xc2xe, ⅕, ⅖, ⅗, etc. (i.e., integral fractions) of the intensity range.
The inventor of this application has previously proposed one technique for reducing the existence of artifacts. Thus, in U.S. Pat. No. 5,737,453, xe2x80x9cEnhanced Error-Diffusion Method For Color Or Black-And-White Reproductionxe2x80x9d, the inventor herein proposed a technique for reducing halftoning artifacts by adjusting the threshold used in the halftoning decision, and by adjusting the coefficients of weights used to diffuse error. The technique described therein produced significantly reduced structural artifacts through a process that can inaccurately be conceptualized as introducing noise into the thresholding and the error diffusion process.
The inventor has since recognized that improved performance can be obtained by adjusting the amount of noise introduced into the thresholding and error diffusion process based on the amount of higher frequency spatial characteristics of the input image, such that when an input image naturally possesses a fair degree of noise (as is often the case when the input image is a natural image rather than a computer-generated image), there is less reason to introduce additional noise into the halftoning process.
It is an object of the invention to capitalize on the inventor""s recognition that certain images need lesser amounts of noise injected into the halftoning and error diffusion process, by providing improved error diffusion halftoning.
According to one aspect of the invention, plural threshold masks are provided for use during error diffusion processing. Each thresholding mask has only a limited number of values, such as three values, with two of the values being centered around a central value, and with each different one of the plural threshold masks being provided for a different segment of the input intensity range. Preferably, a separate threshold mask is provided for each and every input intensity value. The spread of values in each threshold mask varies based on its corresponding intensity level. The spread increases at each intensity range corresponding to formation of artifacts, and results, for example, in a large spread at xc2xd of the intensity range, and correspondingly smaller spreads at ⅓, xc2xc, ⅕, etc. of the intensity range. At intervening non-integral fractions of the intensity range, the spread is reduced. Preferably, the spread of each intensity mask is derived empirically, based on the input/output characteristics of the overall halftoning process including the printed output of a particular model of printer, so as to result in injection of precisely enough noise to disrupt the formation of artifacts in images of low gradient.
A different threshold mask is selected for halftoning based on the intensity value of the input image. Because each threshold mask provides only the amount of spread needed to disrupt formation of artifacts, noise is not unnecessarily injected into the overall halftoning process.
In a further aspect, the invention decides whether to apply a selected one of the threshold masks, or whether to apply a fixed threshold such as 50% gray, based on the presence of high frequency spatial characteristics of the input image. Preferably, the presence of high frequency spatial characteristics of the input image is determined based on a simple gradient test, so that the gradient at each target pixel of the halftoning process is determined based on whether there is a significant (for example, two or three levels out of 256 intensity levels) change relative to adjacent pixels. If there is a significant change from adjacent pixels, then a fixed threshold is applied in the halftoning process; on the other hand, if there is not a significant change, then one of the predetermined threshold masks is selected based on the intensity level of the input image.
Thus, in this aspect of the invention, whether to apply a threshold mask or a fixed threshold is decided based on local image gradient. Because the decision as to whether to use a threshold mask or a fixed threshold is made based on local gradient and/or high frequency spatial characteristics, the invention avoids unnecessary injection of image noise in those areas of the image which by themselves already have sufficient spatial characteristics to avoid formation of artifacts.
In a related aspect of the invention, the range of input intensities is divided into plural segments, with different error diffusion weights being provided for each different segment. In the aforementioned U.S. Pat. No. 5,737,453, which is incorporated herein by reference as if set forth in full, different error diffusion weights were provided at highlight areas of an image, such as extremely light and extremely dark areas. In the present invention, an additional segment is provided at the mid-tone (i.e., 50% gray) segment, with weights in the mid-tone segments being selected so as to decrease the tendency of the error diffusion process to form regular checkerboard patterns. Specifically, in U.S. Pat. No. 5,737,453, error diffusion weights in highlight areas were selected to provide very stable and even distribution of errors, so as to cause a corresponding stable and even distribution of printed dots with reduced worm-like artifacts. In contrast, in the mid-tone segment of the present invention, error diffusion weights are selected to provide unstable and odd distribution of errors, with a corresponding unstable and odd distribution of printed dots so as to prevent formation of an even checkerboard pattern. Thus, error diffusion coefficients in highlight and mid-tone segments are preferably different; and preferably there is a transition region around the mid-tone segment from standard error diffusion weights to the specialized weights of the invention""s mid-tone segment.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiment thereof in connection with the attached drawings.